1. Field of the Invention
The present invention relates to data networking and in particular to optimizing data link utilization in an intermediate network node.
2. Background Information
A computer network is a geographically distributed collection of interconnected communication links and segments for transporting data between nodes, such as personal computers and workstations. The nodes typically transport the data over the network by exchanging discrete frames or packets containing the data in accordance with various pre-defined protocols, such as the Transmission Control Protocol/Internet Protocol (TCP/IP) or the Internetwork Packet eXchange (IPX) protocol.
Many types of networks are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). LANs typically connect nodes over dedicated private communications links located in the same general physical location, such as a building or a campus. WANs, on the other hand, typically connect large numbers of geographically dispersed nodes over long-distance communications links, such as common carrier telephone lines. The Internet is an example of a WAN that connects disparate networks throughout the world, providing global communication between nodes contained in various networks.
WANs typically comprise a complex network containing many different intermediate network nodes, such as routers or switches, interconnected to form the WAN. Data (traffic) carried by the intermediate nodes often originate from various different sources, such as source nodes coupled to the WAN, and are destined for various destinations, such as destination nodes also coupled to the WAN. At each intermediate node, traffic may arrive at various times and rates and, consequently, cause the intermediate node to become congested. Congestion, in turn, may lead to delays in delivering the traffic through the intermediate node. Such delays may not be tolerable for time-sensitive data, such as digitized voice data; thus, for certain types of traffic, it may be desirable to provide a guaranteed level of service to ensure timely delivery of the traffic.
One way to provide a guaranteed level of service between source and destination end nodes connected via a WAN is to establish a data flow, such as a virtual connection (VC), between the nodes, wherein the data flow is associated with a “committed rate” component, such as a committed information rate (CIR). A CIR defines the level of service provided by the data flow and is a guarantee (contract) of a certain end-to-end bandwidth between the nodes.
Intermediate nodes carrying the data flow typically reserve (commit) resources that are sufficient to ensure the bandwidth set forth by the CIR is available to the data flow. For example, assume two end nodes are connected to a WAN comprising a plurality of intermediate nodes and the nodes utilize a VC associated with a CIR of 64-kilobits-per-second (Kbps). Each intermediate node carrying the data flow would commit sufficient resources to the VC to meet the VC's CIR bandwidth requirement, i.e., 64-Kbps.
In a typical WAN arrangement, the intermediate nodes are interconnected via high-speed (data) links that are generally capable of carrying data at rates much higher than the rates generated by the individual end-nodes. This enables the intermediate nodes to carry several data flows on a link. For example, a data link coupling two intermediate nodes may be capable of carrying data at a rate of 1.544 Megabits-per-second (Mbps), whereas, end-nodes coupled to the intermediate nodes may only generate data at a peak rate of 64-Kbps. Thus, the data link has sufficient capacity to carry up to 24 VCs, each of which is associated with a CIR of 64-Kbps.
In addition to being associated with a CIR component a data flow may also be associated with an “excess rate” component, such as an excess information rate (EIR). An EIR specifies a data rate (in, e.g., bits-per-second) in excess of the CIR that a data flow can “burst” onto the data flow at a particular intermediate node when the intermediate node is not congested. Unlike the CIR, the EIR is not a guaranteed rate; thus, the intermediate nodes carrying the data flow do not commit resources to guarantee the EIR. Rather, the intermediate nodes utilize excess capacity, when available, to provide for the EIR.
A packet buffer is often employed in an intermediate node to temporarily hold packets processed by the node. The packet buffer often comprises one or more memory devices that are arranged to form one or more First-In First-Out (FIFO) output queues, wherein each queue may be associated with a particular data flow, e.g., a VC. Moreover, the intermediate node may employ a scheduler to determine when packets are removed from an output queue and transferred onto the network. The scheduler, in turn, may employ one or more calendar queues that are used to determine the time when a particular packet is removed from a particular output queue.
Often when a packet is removed from an output queue, the scheduler examines the rate information associated with the output queue's data flow, such as the CIR and EIR components of the data flow. The scheduler may use this information to determine a future time, which represents the time when the next packet is removed from the output queue in order for the data flow to be compliant with the rate information. The scheduler may then place a queue identifier (QID) that identifies the output queue in an entry (time slot) in the calendar queue corresponding with the future time. As time advances and the entry reaches the head of the calendar queue, the scheduler typically removes the next packet from the output queue associated with the QID contained in the entry. The scheduler may then schedule a future time for a subsequent packet to be removed from the output queue in a manner as described above.
One problem with above arrangement is that if the data flow contains an EIR component, the future time slot determined for the data flow may be less than optimal with respect to data link utilization. For example, if a VC contains both CIR and EIR components and the data link associated with the VC is congested at the time a future time slot is determined, the scheduler may assume the data link does not have excess capacity available to accommodate the EIR component. Thus, the scheduler may only use the CIR component to determine the time slot for the VC. Consequently, the determined time slot may be later in time than it would be if the EIR component were included in the determination. If shortly after the determination is made the data link suddenly becomes idle (i.e., has excess capacity), the data flow may not be able to take advantage of the link's sudden excess capacity as the determined time slot may not be at the head of the calendar queue. As a consequence, the data link may become underutilized.
One possible solution to this problem is to remove the earliest entry in the calendar queue associated with an output queue whose data flow contains an EIR component, and transfer data from the output queue onto the data link when the data link becomes idle. However, this solution is complex and may be time consuming as it may involve, inter alia, scanning and removing entries from the calendar queue. Moreover, depending on the configuration of the scheduler this solution may be difficult to implement. For example, if the scheduler is implemented using logic gates, the number of gates involved in scanning and modifying the calendar queue may become quite impractical.